#include <fstream>
#include <iostream>

using namespace std;

const int BOARD_WIDTH = 9;
const int MAX_KINGS   = 2;

int line[BOARD_WIDTH+2] = {0};    // 记录第i行国王的个数 
int col [BOARD_WIDTH+2] = {0};    // 记录第i列国王的个数 
int mate[BOARD_WIDTH+2] = {0};    // 记录第i个3*3矩阵中国王的个数

// 记录棋盘board[n][c]==0表示空位置， board[n][c]==1表示该位置放有国王
int board[BOARD_WIDTH+2][BOARD_WIDTH+2] = {0};
int total_count = 0;

bool isPlaceOK(int n, int c) {
    // 检查第n行是否已有M个国王 
    if (line[n] >= MAX_KINGS) return false;
    // 检查第c列是否已有M个国王 
    if (col [c] >= MAX_KINGS) return false;
    // 检查位置[n,c]所在的3*3矩阵中的国王个数是否已经大于M个
    int k = (int)((n-1)/3)*3 + (int)((c-1)/3);
    if (mate[k] >= MAX_KINGS) return false;

    //检查n-1行的c-1, c, c+1位置是否有国王 
    if (board[n-1][c] | board[n-1][c-1] | board[n-1][c+1])  return false;
    //检查n行的c-1, c+1位置是否有国王 
    if (board[n][c-1] | board[n][c+1])                      return false;
    //检查n+1行的c-1, c, c+1位置是否有国王 
    if (board[n+1][c] | board[n+1][c-1] | board[n+1][c+1])  return false;

    return true;
}

void printSol() {
    cout << "Solution: " << total_count << endl;
    for (int i = 1; i <= BOARD_WIDTH; ++i) {
        for (int j = 1; j <= BOARD_WIDTH; ++j) {
            cout << board[i][j] << "  ";
        }
        cout << endl;
    }
    cout << endl;
}

void addKings(int n, int c) {
    if (c > BOARD_WIDTH) return ;
    if (n > BOARD_WIDTH) {
        total_count++;
        printSol();
        return ;
    }
    //从第c列开始遍历
    while (c <= BOARD_WIDTH) {
        if (isPlaceOK(n, c)) {
            //如果可以放置，就把国王放在第n行第c列
            col [c]++;
            line[n]++;
            int k = (int)((n-1)/3)*3 + (int)((c-1)/3);
            mate[k]++;
            board[n][c] = 1;   //将board[n][i]置为1，表示将国王放在该位置 
            if (line[n] == MAX_KINGS) {
                addKings(n+1, 1);
            } else {
                addKings(n, c+1);
            }
            board[n][c] = 0;    //当回溯(查找新方案)时，需要清除原来的痕迹
            mate[k]--;
            col [c]--;
            line[n]--;
        }
        c++;
    }
 
}

int main() {
    static std::ofstream g_log("result.txt");
    std::cout.rdbuf(g_log.rdbuf());

    addKings(1,1);

    cout << "total: " << total_count << " solutions.\n";
    return 0;
}
